package leetcode.editor.cn;
//给定一个二叉树，返回它的中序 遍历。 
//
// 示例: 
//
// 输入: [1,null,2,3]
//   1
//    \
//     2
//    /
//   3
//
//输出: [1,3,2] 
//
// 进阶: 递归算法很简单，你可以通过迭代算法完成吗？ 
// Related Topics 栈 树 哈希表 
// 👍 721 👎 0

import leetcode.editor.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;

//Java：二叉树的中序遍历
class P94BinaryTreeInorderTraversal {
    public static void main(String[] args) {
        Solution solution = new P94BinaryTreeInorderTraversal().new Solution();
        // TO TEST
        TreeNode treeNode = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
        List<Integer> integers = solution.inorderTraversal(treeNode);
        System.out.println(integers.toString());
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     */
/*    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }*/

    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            // 递归实现
            Consumer<TreeNode> recursion = new Consumer<TreeNode>() {
                @Override
                public void accept(TreeNode node) {
                    if (node == null) {
                        return;
                    }
                    // 左中右顺序
                    this.accept(node.left);
                    result.add(node.val);
                    this.accept(node.right);
                }
            };
            recursion.accept(root);
            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}